package com.itheima.datastructure.stack;

import java.util.HashMap;
import java.util.Map;

/**
 * 有效的括号
 */
public class E01Leetcode20 {

    public boolean isValid(String s) {
        ArrayStack<Character> stack = new ArrayStack<>(s.length());
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') { // 左括号,则右括号入栈
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else {
                // 如果是 )、]、} 则和栈顶元素对比
                if (!stack.isEmpty() && c == stack.peek()) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public boolean isValid01(String s) {
        ArrayStack<Character> stack = new ArrayStack<>(s.length());
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 栈为空
            boolean empty = stack.isEmpty();
            if (empty) {
                // 栈为空, 则直接入栈
                stack.push(c);
            } else {
                // 栈不为空, 则对比栈顶元素
                Character top = stack.peek();
                Character match = getMatch(c);
                if (match != null && match.equals(top)) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }

        return stack.isEmpty();
    }

    private static Character getMatch(char c) {
        if (c == ')') {
            return '(';
        }
        if (c == ']') {
            return '[';
        }
        if (c == '}') {
            return '{';
        }
        return null;
    }

    /*
        (   [   ]

        底 - 栈 - 顶
        )

        遇到左括号, 把要配对的右括号放入栈顶
        遇到右括号, 把它与栈顶元素对比
            若相等, 栈顶元素弹出, 继续对比下一组
            若不等, 无效括号直接返回 false
     */

    public static void main(String[] args) {
        E01Leetcode20 s = new E01Leetcode20();
        System.out.println(s.isValid01("([{}])"));
        System.out.println(s.isValid01("([{{}}])"));
        System.out.println(s.isValid01("()[]{}"));
        System.out.println(s.isValid01("()"));
        System.out.println("---------------------");

        System.out.println(s.isValid01("[)"));
        // ]
        System.out.println(s.isValid01("([)]"));
        // ) ]
        System.out.println(s.isValid01("([]"));
        // )
        System.out.println(s.isValid01("("));

        System.out.println("---------------------");
        System.out.println(s.isValid01(")("));
        System.out.println(s.isValid01("]"));
    }

}
